public class Solution01 {
	// 第一个大于的节点
	private TreeNode firstGreaterNode;
	// 最后一个小于的节点
	private TreeNode lastLowerNode;
	private TreeNode preNode;

	public void recoverTree(TreeNode root) {
		dfs(root);
		if (firstGreaterNode != null && lastLowerNode != null) {
			int temp = firstGreaterNode.val;
			firstGreaterNode.val = lastLowerNode.val;
			lastLowerNode.val = temp;
		}
	}

	public void dfs(TreeNode root) {
		if (root != null) {
			dfs(root.left);
			if (preNode != null && preNode.val > root.val) {
				if (firstGreaterNode == null) {
					firstGreaterNode = preNode;
				}
				lastLowerNode = root;
			}
			preNode = root;
			dfs(root.right);
		}
	}
}
